#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
typedef char KeyType;

typedef struct node
{
    KeyType key;
    int count;
    struct node *left;
    struct node *right;
} BSTNode;

BSTNode *SearchBST(BSTNode *root, KeyType k)
{
    if (root == NULL || root->key == k)
        return root;
    if (k < root->key)
        return SearchBST(root->left, k);
    else
        return SearchBST(root->right, k);
}

BSTNode *InsertBST(BSTNode *root, KeyType k)
{
    BSTNode *p = SearchBST(root, k);
    if (p != NULL)
        p->count++;
    else
    {
        if (root == NULL)
        {
            root = (BSTNode *)malloc(sizeof(BSTNode));
            root->key = k;
            root->count = 1;
            root->left = root->right = NULL;
        }
        else if (k < root->key)
            root->left = InsertBST(root->left, k);
        else if (k > root->key)
            root->right = InsertBST(root->right, k);
    }
    return root;
}

BSTNode *CreateBST(KeyType a[], int n)
{
    BSTNode *root = NULL;
    for (int i = 0; i < n; i++)
    {
        root = InsertBST(root, a[i]);
    }
    return root;
}

void DestoryBSTree(BSTNode *&root)
{
    if (root != NULL)
    {
        DestoryBSTree(root->left);
        DestoryBSTree(root->right);
        free(root);
    }
}

BSTNode *DeleteBST(BSTNode *root, KeyType k)
{
    if (root == NULL)
        return NULL;
    BSTNode *p = root, *fu = NULL;
    while (p != NULL)
    {
        if (p->key == k)
            break;
        fu = p;
        if (k < p->key)
            p = p->left;
        else
            p = p->right;
    }
    if (p == NULL) //树中没有该节点
        return root;
    if (p->left == NULL && p->right == NULL) // p节点为叶子节点
    {
        if (p == root)
            root = NULL;
        else
        {
            if (fu->left == p)
                fu->left = NULL;
            else
                fu->right = NULL;
        }
        free(p);
    }
    else if (p->right == NULL) //若p节点的右孩子为空
    {
        if (fu == NULL)
            root = root->left;
        else
        {
            if (fu->left == p) // p为双亲节点的左孩子
                fu->left = p->left;
            else
                fu->right = p->left;
        }
        free(p);
    }
    else if (p->left == NULL) //若p节点的左孩子为空
    {
        if (fu == NULL)
            root = root->right;
        else
        {
            if (fu->left == p) // p为双亲节点的左孩子
                fu->left = p->right;
            else
                fu->right = p->right;
        }
        free(p);
    }
    else // p的左孩子右孩子都不为空(可以用左子树中最大的节点q的值代替p节点的值，然后删除q节点,q节点属于无右子树情况)
    {
        BSTNode *q = p->left;
        fu = q;
        while (q->right != NULL)
        {
            fu = q;
            q = q->right;
        }
        p->key = q->key;
        if (q == fu->left)
            fu->left = q->left;
        else
            fu->right = q->left;
        free(q);
    }
    return root;
}

int Length(char zifu[])
{
    int count = 0;
    while (zifu[count] != '\n')
    {
        count++;
    }
    return count;
}

void InOrder(BSTNode *root)
{
    if (root != NULL)
    {
        InOrder(root->left);
        printf("%c出现次数为：%d\n", root->key, root->count);
        InOrder(root->right);
    }
}

int main()
{
    char zifu[50];
    fgets(zifu, 50, stdin);
    printf("%s", zifu);
    int len = Length(zifu);
    BSTNode *root = CreateBST(zifu, len);
    InOrder(root);
    DestoryBSTree(root);
    return 0;
}